package com.daji.base_data_structure.Graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/* 
 * 这里的图只能存储int元素，就是原生的int类型的图。
 * 图中顶点的实际存储，从0开始，视pointCount决定，
 * 比如pointCount为5，那么这个图的顶点元素就是5个Integer：0，1，2，3，4
 */
public class Graph {
    //顶点数目
    private final int pointCount;
    //边的数目
    private int edgeCount;
    //邻接表(其实表示方式也是二维数组)
    private List<Queue<Integer>> table;

    //标记数组:索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] markedArr;

    public Graph(int pointCount){
        //初始化顶点数量
        this.pointCount = pointCount;
        //初始化边的数量
        this.edgeCount = 0;
        //初始化邻接表
        this.table = new ArrayList<>();   
        //初始化标记数组（默认全都是false）
        this.markedArr = new boolean[pointCount];

        for (int i = 0; i < pointCount; i++) {
            //LinkedList实现了Queue，Queue是父，LinkedList是子，自动转换。
            //相当于 new Queue<Integer>
            //邻接表的每一个元素都存放了一个队列，该队列会存储和table[i]相链接的所有顶点
            table.add(new LinkedList<Integer>()); 
        }
    }


    //获取顶点数目
    public int getPointCount(){
        return pointCount;
    }

    //获取边的数目
    public int getEdgeCount(){
        return edgeCount;
    }

    //向图中添加一条边 v-w
    public void addEdge(int point1, int point2) {
        //在无向图中，边是没有方向的，所以该边既可以说是从v到w的边，又可以说是从w到v的边，因此，需要让w出现在v的邻接表中，并且还要让v出现在w的邻接表中

        table.get(point1).offer(point2);  //offer相当于enqueue；
        table.get(point2).offer(point1);
        //边的数量+1
        edgeCount++;

    }

    //获取和顶点v相邻的所有顶点
    public Queue<Integer> getSpecificPointAllNeighbors(int point){
        return table.get(point);
    }


    /**
     * 使用深度优先搜索找出图中s顶点的所有相通顶点
     * （其实就是前序遍历，只不过要将搜索过的进行标记，因为图是有闭合环的）
     * @param s
     * @return 所有相通顶点构成的数组
     */
    public List<Integer> depthFirstSearch(int s){

        List<Integer> points = new ArrayList<>();
        dfs(points,s);

        //将所有标记清空成false
        for (int i = 0; i < markedArr.length; i++) {
            this.markedArr[i] = false;
        }
        //清理结束
        return points;
    }
    private void dfs(List<Integer> points, int point){
        //把当前顶点（自己）标识为已搜索
        this.markedArr[point] = true;
        
        //得到该点的所有邻居
        Queue<Integer> neighbors = this.table.get(point);
        for (Integer perNeighbor : neighbors) {
            //判断当前顶点有没有被搜索过，如果没有被搜索过，则递归调用dfs方法进行深度搜索
            if(this.markedArr[perNeighbor] == false){
                //塞入相通顶点数组
                points.add(perNeighbor);
                dfs(points, perNeighbor);
            }
        }
    }

    /**
     * 使用广度优先搜索找出图中s顶点的所有相通顶点
     * （其实就是层序遍历，只不过要将搜索过的进行标记，因为图是有闭合环的）
     * 使用队列辅助层序遍历
     * @param s 
     * @return 所有相通顶点构成的数组
     */
    public List<Integer> breadthFirstSearch(int s){

        //声明辅助队列进行遍历
        Queue<Integer> workQueue = new LinkedList<Integer>();
        //所有相通顶点构成的数组
        List<Integer> points = new ArrayList<>();

        //标记该顶点为已遍历
        this.markedArr[s] = true;
        workQueue.offer(s); //enqueue

        //广度优先搜索
        while (workQueue.size() != 0) {
            Integer point = workQueue.remove(); //dequeue
            //得到该点的所有邻居
            Queue<Integer> neighbors = this.table.get(point);
            for (Integer perNeighbor : neighbors) {
                //如果该节点没被遍历过，对其进行操作
                if (this.markedArr[perNeighbor] == false) {
                    workQueue.offer(perNeighbor);   //enqueqe 入队
                    points.add(perNeighbor);
                    this.markedArr[perNeighbor] = true; //标记该顶点为已遍历
                }
                
            }
        }
        //将所有标记清空成false
        for (int i = 0; i < markedArr.length; i++) {
            this.markedArr[i] = false;
        }
        //清理结束
        return points;
    }

}